package exercises.leetcode;

import exercises.newcoder.util.ListNode;

/**
 * <a href="https://leetcode-cn.com/problems/split-linked-list-in-parts/">
 * 725. 分隔链表</a>
 *
 * <p><span color="#87CEEB">描述:</span>
 * 给你一个头结点为 head 的单链表和一个整数 k ，请你设计一个算法将链表分隔为 k 个连续的部分。
 * <p>
 * 每部分的长度应该尽可能的相等：任意两部分的长度差距不能超过 1 。这可能会导致有些部分为 null 。
 * <p>
 * 这 k 个部分应该按照在链表中出现的顺序排列，并且排在前面的部分的长度应该大于或等于排在后面的长度。
 * <p>
 * 返回一个由上述 k 部分组成的数组。
 *
 * @author or2
 * @date 2021年09月22日 时间: 18:42
 */
public class No725 {
    public ListNode[] splitListToParts(ListNode head, int k) {
        ListNode[] ans = new ListNode[k];

        ListNode p = head;
        int length = 0;
        while (p != null) {
            length++;
            p = p.next;
        }

        int per = length / k;
        int rest = length % k;
        p = head;
        for (int i = 0; i < rest; i++) {
            ans[i] = p;
            for (int j = 0; j < per; j++) {
                p = p.next;
            }
            ListNode temp = p.next;
            p.next = null;
            p = temp;
        }

        if (per == 0) {
            return ans;
        }

        for (int i = rest; i < k-1; i++) {
            ans[i] = p;
            for (int j = 0; j < per - 1; j++) {
                p = p.next;
            }
            ListNode temp = p.next;
            p.next = null;
            p = temp;
        }
        ans[k - 1] = p;

        return ans;
    }
}
